/// @tags: ConvexOptimazition DPwithMonotoneStack MonotoneDecision
#include <cstdio>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef long long LL;

int const N = 5e5 + 5;

int n, m, k, top;
int pos[N], cnt[N], stk[N], a[N];
LL res;
LL f[N], sum[N];

inline LL w(int l, int r) {
  LL h = (l + r + 1) >> 1;
  LL res = sum[r] - sum[h];
  LL d1 = (LL)(h - l) * a[h];
  LL d2 = (LL)(r - h) * a[h];
  return res - d2 + d1 - sum[h] + sum[l];
}

inline LL calc(LL j, LL i) { return f[j] + w(j, i); }

inline bool check(LL x) {
  stk[top = 0] = 0;
  int h = 0;
  pos[0] = 1;
  for (int i = 1; i <= n; ++i) {
    while (h < top && pos[h] < i) h++;
    if (pos[h] > i) h--;
    f[i] = calc(stk[h], i) - x, cnt[i] = cnt[stk[h]] + 1;
    while (top && calc(stk[top], pos[top]) >= calc(i, pos[top])) top--;
    int l = pos[top], r = n + 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      calc(stk[top], mid) >= calc(i, mid) ? r = mid : l = mid + 1;
    }
    if (l <= n) stk[++top] = i, pos[top] = l;
  }
  res = f[n] + x * m;
  return cnt[n] < m;
}

inline int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i], sum[i] = sum[i - 1] + a[i];
  int l = -1e9, r = 0, mid;
  pos[0] = 1;
  sum[n + 1] = sum[n];
  while (l < r) {
    mid = (l + r) >> 1;
    check(mid) ? l = mid + 1 : r = mid;
  }
  check(l);
  cout << res;
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P6246 [IOI2000] 邮局 加强版.in", "r", stdin);
  freopen("P6246 [IOI2000] 邮局 加强版.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
